package list;

public class LinkedList<E> extends AbstractList<E>{
	
	private Node<E> first;
	private Node<E> last;
	
	@Override
	public void add(int index, E element) {
		checkIndexForAdd(index);
		
		if (index == size) {	// 在链表的最后面添加节点
			last = new Node<>(last, element, null);
			if (last.prev == null) {	// 在最后添加节点并且该节点是链表第一个添加的节点
				first = last;
			} else {
				last.prev.next = last;
			}
		} else {	// 在链表中间插入节点
			Node<E> next = node(index);
			Node<E> prev = next.prev;
			Node<E> node = new Node<>(prev, element, next);
			if (prev == null) {
				first = node;
			} else {	// 插入的位置为头节点
				prev.next = node;
			}
			next.prev = node;
		}
		size++;
	}
	
	@Override
	public E remove(int index) {
		checkIndex(index);
		Node<E> node = node(index);
		Node<E> prev = node.prev;
		Node<E> next = node.next;
		
		if (prev == null) {
			first = next;
		} else {
			prev.next = next;
		}
		
		if (next == null) {
			last = prev;
		} else {
			next.prev = prev;
		}
		
		size--;
		return node.element;
	}
	
	@Override
	public E get(int index) {
		return node(index).element;
	}

	@Override
	public E set(int index, E element) {
		Node<E> node = node(index);
		E oldElement = node.element;
		node.element = element;
		return oldElement;
	}

	

	@Override
	public int indexOf(E element) {
		if (element == null) {
			Node<E> node = first;
			for (int i = 0; i < size; i++) {
				if (node.element == null) return i;
				node = node.next;
			} 
		} else {
			Node<E> node = first;
			for (int i = 0; i < size; i++) {
				if (element.equals(node.element)) return i;
				node = node.next;
			} 
		}
		return ELEMENT_NOT_FOUND;
	}

	@Override
	public void clear() {
		size = 0;
		first = null;
		last = null;
	}
	
	private Node<E> node(int index) {
		checkIndex(index);
		if (index < size >> 1) {	// 从前面开始找
			Node<E> node = first;
			for (int i = 0; i < index; i++) {
				node = node.next;
			}
			return node;
		} else {	// 从后面开始找
			Node<E> node = last;
			for (int i = size - 1; i > index; i--) {
				node = node.prev;
			}
			return node;
		}
	}
	
	private static class Node<E> {
		Node<E> prev;
		Node<E> next;
		E element;
		
		public Node(Node<E> prev, E element, Node<E> next) {
			this.prev = prev;
			this.element = element;
			this.next = next;
		}
	}
	
}
